package 剑指offer;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author zhangmin
 * @create 2021-12-07 9:26
 */
public class day27_591_592 {

    /**==============================================================================================================================================
     * 剑指 Offer 59 - I. 滑动窗口的最大值
     * 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
     * 单调队列：
     * */
    class MonotonicQueue{
        // 双链表，支持头部和尾部增删元素
        private LinkedList<Integer> q = new LinkedList<>();

        public void push(int n){
            while (!q.isEmpty()&&q.getLast()<n){
                q.pollLast();
            }
            q.addLast(n);
        }
        public int max(){
            return q.getFirst();
        }
        public void pop(int n){
            //可能要删除的元素已经被压缩了,就不需要删除了
            if (q.getFirst()==n){
                q.pollFirst();
            }
        }
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length==0||k==0||k>nums.length) return new int[0];
        //利用单调队列来记录窗口内的最大值
        MonotonicQueue queue=new MonotonicQueue();
        ArrayList<Integer> res=new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (i<k-1) {
                queue.push(nums[i]);
            } else {
                //将i如窗口
                queue.push(nums[i]);
                //刚好窗口内为k个元素
                res.add(queue.max());
                //将窗口中第一个元素删除
                queue.pop(nums[i-k+1]);
            }
        }
        int[] resint=new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            resint[i]=res.get(i);
        }
        return resint;
    }

    /**==============================================================================================================================================
     * 剑指 Offer 59 - II. 队列的最大值
     * 请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
     * 若队列为空，pop_front 和 max_value 需要返回 -1
     * 单调队列+辅助队列记录元素
     * */
    class MaxQueue {

       // 双链表，支持头部和尾部增删元素
        private LinkedList<Integer> q = new LinkedList<>();
        private Deque<Integer> d=new LinkedList<>();

        public MaxQueue() {

        }

        public int max_value() {
            if (d.isEmpty()){
                return -1;
            }
            return q.getFirst();
        }

        public void push_back(int value) {
            while (!q.isEmpty()&&q.getLast()<value){
                q.pollLast();
            }
            q.addLast(value);
            d.addLast(value);
        }

        public int pop_front() {
            if (d.isEmpty()) return -1;
            int n=d.pop();
            if (n==q.getFirst()){
                q.pollFirst();
            }
            return n;
        }
    }
}
